#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "EasyBMP.h"

#define SIZE 250
#define BASE 10
#define PARTICLES 1000
#define MAX 0

int A[SIZE][SIZE];

int check()
{
    
    int X[SIZE * SIZE];
    int Y[SIZE * SIZE];
    int used[SIZE][SIZE];
    int x, y, sp1, sp2, white;
    
    white = 0;
    for(x = 0; x < SIZE; x++)
        for(y = 0; y < SIZE; y++) {
            white += A[x][y];
            used[x][y] = 0;
        }
    
    while(!A[x][y]) {
        x = rand() % SIZE;
        y = rand() % SIZE;
    }
    X[0] = x;
    Y[0] = y;
    white--;
    used[x][y] = 1;
    sp1 = 0;
    sp2 = 1;
    
    while(sp1 != sp2) {
        x = X[sp1]; y = Y[sp1];
        sp1 = (sp1 + 1) % (SIZE * SIZE);
        if(x > 0)
            if((!used[x - 1][y])&&(A[x - 1][y])) {
                X[sp2] = x - 1;
                Y[sp2] = y;
                sp2 = (sp2 + 1) % (SIZE * SIZE);
                used[x - 1][y] = 1;
                white--;
            }
        if(y > 0)
            if((!used[x][y - 1])&&(A[x][y - 1])) {
                X[sp2] = x;
                Y[sp2] = y - 1;
                sp2 = (sp2 + 1) % (SIZE * SIZE);
                used[x][y - 1] = 1;
                white--;
            }
        if(x < SIZE - 1)
            if((!used[x + 1][y])&&(A[x + 1][y])) {
                X[sp2] = x + 1;
                Y[sp2] = y;
                sp2 = (sp2 + 1) % (SIZE * SIZE);
                used[x + 1][y] = 1;
                white--;
            }
        if(y < SIZE - 1)
            if((!used[x][y + 1])&&(A[x][y + 1])) {
                X[sp2] = x;
                Y[sp2] = y + 1;
                sp2 = (sp2 + 1) % (SIZE * SIZE);
                used[x][y + 1] = 1;
                white--;
            }
    }
    //printf("%d\n",white);
    if(white) return 0;
    //printf("win\n");
    return 1;
}

int check_sqr(int x, int y)
{
    //return 1;
    if(x > 0) {
        if(y > 0)
            if((A[x][y]) && (A[x - 1][y]) && (A[x][y - 1]) && (A[x - 1][y - 1]))
                return 0;
        if(y < SIZE - 1)
            if((A[x][y]) && (A[x - 1][y]) && (A[x][y + 1]) && (A[x - 1][y + 1]))
                return 0;
    }
    if(x < SIZE - 1) {
        if(y > 0)
            if((A[x][y]) && (A[x + 1][y]) && (A[x][y - 1]) && (A[x + 1][y - 1]))
                return 0;
        if(y < SIZE - 1)
            if((A[x][y]) && (A[x + 1][y]) && (A[x][y + 1]) && (A[x + 1][y + 1]))
                return 0;
    }
    return 1;
}

int main(int argc, char *argv[])
{    
    int X[PARTICLES], Y[PARTICLES];
    int i, j, x, y, total;
    
    BMP Output;
    RGBApixel PB, PW ,NewPixel;
    
    srand( time(0) );
    
    for(i = 0; i < SIZE; i++)
        for(j = 0; j < SIZE; j++)
            A[i][j] = 0;
    for(i = 0;i < BASE; i++) {
        do {
            x = rand() % SIZE;
            y = rand() % SIZE;
        } while(A[x][y]);
        A[x][y] = 1;
    }
    
    total = BASE;
    
    for(i = 0; i < PARTICLES; i++) {
        do {
            x = rand() % SIZE;
            y = rand() % SIZE;
        } while(A[x][y]);
        X[i] = x;
        Y[i] = y;
    }
    
    while((total < MAX)||(!check())) {
        //printf("TOTAL %d\n", total);
        for(i = 0; i < PARTICLES; i++) {
            j = rand() % 4;
            switch(j) {
                case 0:
                    X[i] = (X[i] + 1) % SIZE;
                    break;
                case 1:
                    Y[i] = (Y[i] + 1) % SIZE;
                    break;
                case 2:
                    X[i] = (X[i] - 1 + SIZE) % SIZE;
                    break;
                case 3:
                    Y[i] = (Y[i] - 1 + SIZE) % SIZE;
                    break;
            }
            x = X[i]; y = Y[i];
            if(((x > 0) && (A[x - 1][y])) || ((y > 0) && (A[x][y - 1])) ||
                    ((x < SIZE - 1) && (A[x + 1][y])) || ((y < SIZE - 1) && (A[x][y + 1]))) {
                A[x][y] = 1;
                if(!check_sqr(x, y)) {
                    A[x][y] = 0;
                    total--;
                }
                while(A[X[i]][Y[i]]) {
                    X[i] = rand()%SIZE;
                    Y[i] = rand()%SIZE;
                }
                total++;
            }
        }
    }
    
    Output.SetSize(SIZE * 2, SIZE * 2);
    PB.Red = 0;
    PB.Blue = 0;
    PB.Green = 0;
    PB.Alpha = 0;
    PW.Red = 0xFF;
    PW.Blue = 0xFF;
    PW.Green = 0xFF;
    PW.Alpha = 0;
    Output.SetBitDepth( 24 );
    
    for(i = 0; i < SIZE; i++)
        for(j = 0; j < SIZE; j++) {
            if(A[i][j])
                NewPixel = PW;
            else NewPixel = PB;
            Output.SetPixel(2 * i, 2 * j, NewPixel);
            Output.SetPixel(2 * i + 1, 2 * j, NewPixel);
            Output.SetPixel(2 * i, 2 * j + 1, NewPixel);
            Output.SetPixel(2 * i + 1, 2 * j + 1, NewPixel);
        }
    
    Output.WriteToFile("result.bmp");
    
    system("PAUSE");
    return 0;
}
